/**
 * @author LKQ
 * @date 2022/2/17 19:41
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}};
        solution.exist(board, "ABCCED");
    }

    public boolean exist(char[][] board, String word) {
        int h = board.length , w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (check(board, visited, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     *
     * @param board 单词表
     * @param visited 是否访问过
     * @param i board[i]
     * @param j board[i][j]
     * @param s 目标字符串
     * @param k 目标字符串第k个字符
     * @return bool
     */
    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            // 当前字符不匹配
            return false;
        }else if (k == s.length() - 1) {
            // 最后一个字符并且匹配成功
            return true;
        }
        visited[i][j] = true;
        // 相邻四个位置
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir: dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                if (!visited[ni][nj]) {
                    boolean flag = check(board, visited, ni, nj, s, k+1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        // 回溯后，访问了该字符需要重置为未访问
        visited[i][j] = false;
        return result;
    }
}
